Problem statement: zenit12ckk

Po večeroch sa na farmárskom sympóziu uskutočňujú neformálne stretnutia a rôzne zábavné aktivity. Farmárka Halucinka tento rok prišla s hrou, ktorá pohltila všetkých. Farmára Jakuba nahnevalo, že stále prehráva a povedal si, že potrebuje program, pomocou ktorého Halucinku porazí.

Túto hru hrajú dvaja hráči, ktorí sa striedajú v ťahaní. Na stole je na kuse papiera napísané prirodzené číslo n. Ťahajúci si zvolí kladné číslo m, ktoré je vlastným podreťazcom čísla n (vlastný podreťazec znamená, že nesmie byť zvolené celé číslo n). Následne je m odpočítané od n a v hre pokračuje druhý hráč. Napríklad, ak je n rovné 2309, hráč na ťahu môže zvoliť a odpočítať čísla 2, 3, 9, 23, 30, 230 alebo 309. Hráč nemôže zvoliť 2309, pretože sú povolené len vlastné podreťazce. Možné nové čísla sú teda 2000, 2079, 2279, 2286, 2300, 2306 a 2307. Hru prehráva hráč, ktorý nedokáže spraviť žiadny ťah (napríklad ak je číslo na stole jednociferné).

Úvodné číslo sa volí náhodne a Halucinka zvykne prenechať prvý ťah súperovi. Váš program zo vstupu prečíta počiatočné číslo n (1 ≤ n ≤ 1,000,000) a poradí Jakubovi, ako spraviť prvý ťah tak, aby pri rozumnom pokračovaní vyhral bez ohľadu na to, ako bude ťahať Halucinka. Vypíšte číslo, ktoré treba odpočítať v prvom ťahu. Ak je viacero možností, vypíšte najmenšie také číslo. V prípade, že ťah vedúci k víťazstvu neexistuje, vypíšte -1.

12

    
  

1

    
  

111

    
  

-1

    
  

1061

    
  

6